#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。

typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100            //顺序表可能达到的最大长度

typedef struct {
    ElemType *elem; //存储空间的基地址
    int length; //当前长度
} SqList;
typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

Status InitList_Sq(SqList &L) { //算法2.1 顺序表的初始化
    //构造一个空的顺序表L
    L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
    if (!L.elem)
        exit(OVERFLOW); //存储分配失败退出
    L.length = 0; //空表长度为0
    return OK;
}

Status GetElem(SqList L, int i, ElemType &e) {//算法2.2　顺序表的取值
    if (i < 1 || i > L.length)
        return ERROR; //判断i值是否合理，若不合理，返回ERROR
    e = L.elem[i - 1]; //elem[i-1]单元存储第i个数据元素
    return OK;
}

int LocateElem_Sq(SqList L, ElemType e) ;

Status ListInsert_Sq(SqList &L, int i, ElemType e) { //算法2.4 顺序表的插入
    //在顺序表L中第i个位置之前插入新的元素e
    //i值的合法范围是1<=i<=L.length+1
    if ((i < 1) || (i > L.length + 1))
        return ERROR; //i值不合法
    if (L.length == MAXSIZE)
        return ERROR; //当前存储空间已满
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
    L.elem[i - 1] = e; //将新元素e放入第i个位置
    ++L.length; //表长增1
    return OK;
}

Status ListDelete_Sq(SqList &L, int i) { //算法2.5 顺序表的删除
    //在顺序表L中删除第i个元素，并用e返回其值
    //i值的合法范围是1<=i<=L.length
    if ((i < 1) || (i > L.length))
        return ERROR; //i值不合法
    for (int j = i; j <= L.length; j++)
        L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
    --L.length; //表长减1
    return OK;
}
//在顺序表L中查找值为e的数据元素，成功返回其位序，失败返回0。
int LocateElem_Sq(SqList L, ElemType e) {
    for (int i = 0; i<L.length;i++){
        if(L.elem[i]==e){
            return i+1;
        }
    }
    return 0;
}
Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    if (i<1 || i>L.length + 1)
        return ERROR;
    if (L.length>= MAXSIZE)
        return ERROR;
    for (int j=L.length-1; j>=i-1;j--)
        L.elem[j + 1]=L.elem[j];
    L.elem[i-1]=e;
    ++L.length;
    return OK;
}
Status ListDelete_Sq(SqList &L, int i) {
    if (i<1 || i>L.length)
        return ERROR;
    for (int j = i; j < L.length; j++)
        L.elem[j-1] = L.elem[j]; 
    --L.length;
    return OK;
}
Status ListOrderInsert(SqList &L, ElemType e) {
    int i = L.length-1; 
    if (L.length==MAXSIZE) {
        return ERROR;
    }
    while (i>=0 && L.elem[i]>e) {
        L.elem[i + 1]=L.elem[i];
        i--;
    }
    L.elem[i + 1]=e;
    L.length++;
    return OK;
}
LNode* LocateElem_L(LinkList L, int e) {
    LNode *p=L->next;
    while (p!=NULL && p->data!=e) {
        p=p->next;
    }
    return p;
}
Status GetElem_L(LinkList L, int i, ElemType &e){
        LNode *p=L->next;
        int j=1;
        while(p!=NULL &&j<i){
            p=p->next;
            j++;
        }
        if(j>i ||p==NULL){
            return ERROR;
        }
        e=p->data;
        return OK;
}
Status ListInsert_L(LinkList &L, int i, ElemType e) {
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL || j>i-1){
        return ERROR;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
Status ListDelete_L(LinkList &L, int i){
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL || j>i-1){
        return ERROR;
    }
    LNode *q=p->next;
    p->next=q->next;
    return OK;
}
int  ListLength_L(LinkList L){
    LNode *p=L;
    int j=0;
    while(p!=NULL){
        p=p->next;
        j++;
    }
    return j-1;
}
Status ListOrderInsert(LinkList & L,ElemType e){
    LNode *p=L;
    while(p->next!=NULL && p->next->data<e){
        p=p->next;
    }
    if(p==NULL){
        return ERROR;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=NULL;
    s->next=p->next;
    p->next=s;
    return OK;
}
void CreateList_R(LinkList &L, int n) {
   L = (LinkList)malloc(sizeof(LNode));
   L->next=NULL;
   LNode *tail=L;
   int x,i;
   for (i=0; i<n;i++){
       cin>>x;
       LNode *newNode=(LNode*)malloc(sizeof(LNode));
       newNode->data=x;
       newNode->next=NULL;
       tail->next=newNode;
       tail=newNode;
   }
}
void CreateList_H(LinkList &L, int n) {
   L =(LinkList)malloc(sizeof(LNode));
   L->next=NULL;
   int x;
   for (int i=n-1;i>=0;i--) 
    {
       cin >> x;
       LNode *newNode=(LNode *)malloc(sizeof(LNode));
       newNode->data=x;
       newNode->next=L->next;
       L->next=newNode;
   }
}
void MergList(LinkList La, LinkList Lb, LinkList &Lc) {
   Lc=La;
   La=La->next;
   Lb=Lb->next;
   Lc->next=NULL;
   LNode *tail=Lc;
   while (La && Lb) {
       if (La->data<=Lb->data) 
        {
           tail->next=La;
           La=La->next;
       } else {
           tail->next=Lb;
           Lb =Lb->next;
       }
       tail=tail->next;
   }
    if (La!=NULL) {
        tail->next=La;
        La=La->next;
    } else {
        tail->next=Lb;
        Lb=Lb->next;
    }
    tail=tail->next;

}

void MergListFun(LinkList La, LinkList Lb, LinkList &Lc) {
   Lc=La;
   La=La->next;
   Lb=Lb->next;
   Lc->next=NULL;
   LNode *tail=Lc;
   while (La && Lb) {
       if (La->data<Lb->data) {
           tail->next=La;
           La=La->next;
       }else if(La->data>Lb->data){
           tail->next=Lb;
           Lb=Lb->next;
       } else {
           tail->next=La;
           La=La->next;
           Lb =Lb->next;
       }
       tail=tail->next;
   }
    if (La!=NULL) {
        tail->next=La;
        La=La->next;
    } else {
        tail->next=Lb;
        Lb=Lb->next;
    }
    tail=tail->next;

}
void Reverse(LinkList &La) {
    LNode *pre=NULL;
    LNode *cur=La->next;
    LNode *next;
    while(cur){
        next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    La->next=pre;
}




